#include <iostream>
using namespace std;
#define int long long
const int N = 1001000;
int a[N], b[N];
signed main() {
    int n;
    cin >> n;
    a[1] = 1;
    a[2] = 2;
    a[3] = 5;
    if(n <= 3) {
        cout << a[n];
        return 0;
    }
    for(int i = 4; i <= n; i++) {
        a[i] = ((a[i - 1] * 2) % 10000 + a[i - 3]) % 10000;
    }
    cout << a[n] << endl;
    return 0;
}